Single decision trees have high variance: flip a few training samples and the entire tree changes.
This unit solves that problem architecturally. We begin with a geometric look at DT decision boundaries
(axis-aligned rectangles), then introduce bootstrap resampling.
We cover ensemble learning in two flavors:
parallel Bagging (Bootstrap Aggregating) and sequential Boosting.
We then introduce Random Forest
and its even more randomized cousin, Extremely Randomized Trees (ExtraTrees).
Learning Objectives
Draw the axis-aligned rectangular decision boundaries of a shallow DT by hand
Perform a hand bootstrap simulation on n=7; estimate the OOB rate \(1 - 1/e \approx 63.2\%\)
Distinguish Bagging (parallel, independent trees, reduce variance) vs. Boosting (sequential, fit residuals, reduce bias)
Train a Random Forest: \(B\) bootstrap trees + \(\sqrt{d}\) random feature subset at every split
Use OOB (Out-Of-Bag) samples as a free validation set; compare RF vs. ExtraTrees vs. single DT
2. Theory
2.1 Geometric Interpretation of DTs — Axis-Aligned Rectangles
Credit-risk toy example: 30 loan applicants (16 default, 14 non-default). Features: Age, Account Balance ($).
A shallow DT learns two splits:
\(\text{Balance} \ge 50{,}000\)? (vertical line)
Else \(\text{Age} \ge 45\)? (horizontal line in the left half-plane)
⚠ Single-DT Geometric Limitations
Cannot express diagonal or curved decision boundaries (e.g., lines of form \(x_1 + x_2 \le t\) require many splits).
High variance: swap a few training points → the rectangle corners move → boundary changes a lot.
Solutions: (a) use many DTs and average them (Random Forest smoothes the boundary), (b) use kernel/boosting variants.
2.2 Bootstrapping — Create Many Datasets From One
Problem: we want to train 500 diverse trees, but we only have one training dataset of size \(n\).
Bootstrapping solves this by drawing \(n\) samples with replacement to form a synthetic
"bootstrap replicate" dataset, also of size \(n\).
2.3 Ensemble Learning Taxonomy
Property
Bagging (e.g., Random Forest)
Boosting (e.g., AdaBoost, Gradient Boosting)
Execution
✅ Parallel — every base learner trained independently
🔁 Sequential — model t+1 depends on model t's residuals
Goal
Reduce variance by averaging
Reduce bias by reweighting hard samples
Base Learner
Deep/high-variance (unlimited-depth trees)
Shallow/low-variance (stumps, depth=1..6)
Weight scheme
Uniform average (or weighted average)
Each model weighted by its accuracy (AdaBoost)
Overfitting
More trees ⇒ never really hurts; convergence OOB
Too many rounds ⇒ overfits (need early stop)
2.4 Bagging (Bootstrap Aggregating)
Given a base learner \(h\) and \(B\) bootstrap samples:
train \(h_b = h(\text{bootstrap-sample-}b)\) for \(b=1..B\).
Aggregate by unweighted average (regression) or majority vote (classification):
2.5 Random Forest — Bagging + Random Feature Subsets
Bagging alone doesn't fully de-correlate trees because they all share the same dominant root split.
Random Forest (Breiman, 2001) injects a second source of randomness:
at every node of every tree, choose the best split from a random subset of \(m_{\text{try}}\) features,
not all \(d\) of them. This decorrelates trees dramatically.
RF Hyperparameter
Default Rule of Thumb
Effect
n_estimators = \(B\)
100…500 (as many as you can afford)
More trees → smoother, more stable. No overfit from too many!
max_features = \(m_{\text{try}}\)
Classification: sqrt(d); Regression: d/3
Small → more de-correlation; too small → underfit.
max_depth
None (grow fully) — RF variance-averaging handles it
For each training sample \((x_i, y_i)\), roughly 36.8% of trees never saw it during bootstrap training.
Use those trees as a validation panel for sample \(i\): average their predictions → OOB prediction.
The full-dataset OOB error is an approximately unbiased estimate of test error — no data wasted!
📌 OOB Usage Recipe
Set oob_score=True in scikit-learn's RandomForestClassifier.
Train on 100 % of training data (no separate validation split needed).
Read model.oob_score_ for an unbiased held-out accuracy estimate.
Use this to tune max_features, n_estimators, min_samples_leaf, etc.
2.7 Extremely Randomized Trees (ExtraTrees)
RF still uses the optimal split threshold for each of the \(m_{\text{try}}\) candidate features.
ExtraTrees (Geurts et al., 2006) goes one step further: for each candidate feature,
it samples the split threshold uniformly at random from that feature's range, then picks the best of those random splits.
ExtraTrees is:
Even faster than RF (no per-feature threshold sweep)
Often marginally better accuracy when features are noisy
Pairs well with RF in a final ensemble (stacking)
3. Interactive Examples
Example 1: Hand Bootstrap — n = 7
Original dataset samples indexed \(\{1,2,3,4,5,6,7\}\). Using a random-number table, one bootstrap replicate draws indices:
[3, 1, 3, 7, 5, 1, 4].
(a) Which original samples are in-bag? Which are OOB?
In-bag (unique): {1, 3, 4, 5, 7} (5/7 ≈ 71.4%).
OOB: {2, 6} — samples never drawn (2/7 ≈ 28.6% ≈ close to 36.8% theoretical for large n).
(b) What is the count (not unique) of each in-bag index in that replicate?
1→2×, 3→2×, 4→1×, 5→1×, 7→1×. (With-replacement sampling naturally produces weights on each in-bag sample.)
Example 2: Majority-Vote Ensemble
5 independent binary classifiers vote on a sample. Their predictions:
\(h_1 = +1,\; h_2 = -1,\; h_3 = -1,\; h_4 = +1,\; h_5 = +1\).
What does majority-vote Bagging output? If the true label is +1, how many individual classifiers are wrong? Is the ensemble right?
Votes: +1 × 3, −1 × 2 → ensemble prediction = +1 (correct).
h₂ and h₃ are wrong (2/5 = 40 % individual error).
Majority-vote ensemble wins despite many weak voters — the core wisdom-of-crowds mechanism!
Example 3: RF max_features Intuition
Binary classification, d = 100 features, n_estimators = 300.
(a) What's the default RF max_features per split? (b) If we set max_features = 1.0 (full d), what method do we recover? (c) If we set it to 1, what happens?
(a) Classification default = ⌊√d⌋ = 10 features per split.
(b) max_features=d = pure Bagging (no feature randomness). Worse de-correlation.
(c) max_features=1 = each split picks one random feature then thresholds it. Extremely aggressive de-correlation at the cost of bias — rarely optimal in practice.
4. Numerical Solutions
Problem 1: Expected OOB Size (Asymptotic)
For very large \(n\), what is the approximate fraction of unique training samples used in any one bootstrap replicate?
📘 Step-by-Step Derivation
Step 1: Probability a specific sample \(i\) is NOT drawn in one draw = \(1 - 1/n\).
Step 2: Over \(n\) independent draws, P(i never drawn) = \((1 - 1/n)^n\).
Step 2 (Prob): RF class probability = fraction of trees voting for class = P̂(DEFAULT) = 0.72.
Step 3 (Uncertainty): 72/28 is a strong vote (> 2:1 ratio) → confident prediction. Compare with a 51/49 vote, which would be near the decision boundary and could benefit from more trees.
Problem 3: Why RF Feature Importances Are More Stable Than Single DT
Two highly correlated features Age and Tenure both predict churn. Compare single-depth-8 DT vs. RF (B=500, m=√d) in terms of how importances are distributed.
📘 Explanation
Single DT: Greedy pick at root selects whichever feature happens to win on this training set (random tie-break). Feature importances will be ~90% on one, ~10% on the other. A different bootstrap sample would flip the ratio.
Random Forest: Because of feature subsampling at each split, ~50 % of splits will have only Age in the candidate set, ~50 % only Tenure. The two features share the credit across 500 trees, giving importances near 50/50. RF importances are far more stable and trustworthy.
5. Try It Yourself
Problem 1 — Bootstrap Replicate (n=5)
Dataset S = {P, Q, R, S, T}. A bootstrap draw yields: [S, S, P, R, P].
List the in-bag unique samples and the OOB samples.
Compute the empirical in-bag fraction and compare to asymptotic 63.2 %.
In-bag unique = {P, R, S}; OOB = {Q, T}.
In-bag = 3/5 = 60 % (close to 63.2 % for n=5 small).
Problem 2 — Weighted (AdaBoost-Style) Vote
Three weak learners have accuracies α₁ = 0.9, α₂ = 0.6, α₃ = 0.6. (α = the log-odds weight used in AdaBoost is ln((1-ε)/ε).)
Compute the signed weight w = 2α − 1 for each, then output the final weighted-vote sign of (−1, +1, +1) predictions.
w₁ = 0.8, w₂ = 0.2, w₃ = 0.2.
Sum = 0.8·(−1) + 0.2·(+1) + 0.2·(+1) = −0.8 + 0.4 = −0.4.
Sign is negative → final prediction = −1 (class 0 / minority class).
The strong classifier (α₁=0.9) overruled two weak ones.
Problem 3 — OOB vs. Holdout Sizing
n_train = 10,000. Compare: (a) 5-fold CV (train size per fold), (b) size of the OOB panel for any single tree in RF (approx), (c) size of the OOB prediction set for the whole RF (all training points have an OOB panel).
(a) 5-fold CV: each fold uses 8,000 for training, 2,000 for validation.
(b) For one tree, OOB ≈ 36.8 % × 10,000 ≈ 3,680 samples.
(c) For the whole RF, every one of the 10,000 training points has an OOB prediction (it's averaged over its specific ~36.8 % of OOB trees) — so full 10,000-point validation set, no data lost to a holdout.
6. Interactive Quiz
Answer all 5 MCQs. Click on an option to get instant feedback.
Your score: 0 / 5
7. Key Takeaways
Single DTs carve the feature space into axis-aligned rectangles. Easy to plot but brittle (high variance). Swap a few training samples → big boundary changes.
Bootstrap = draw n samples with replacement. Asymptotically, each replicate uses ~63.2 % of unique original training points. The other ~36.8 % are Out-of-Bag (OOB) — a free validation set.
Two ensemble paradigms:Bagging (parallel, independent high-variance base learners, average/vote → reduces variance); Boosting (sequential, reweight hard samples or fit residuals → reduces bias).
Random Forest = Bagging + random feature subsets at every split. Defaults: B ∈ [100..500], m_try = ⌊√d⌋. The extra randomness de-correlates trees, which is what makes averaging work dramatically well.
OOB score is your best friend. Set oob_score=True and use the ~unbiased OOB accuracy to tune hyperparameters — no need to waste a validation split on medium/large data.
ExtraTrees = RF + random thresholds per candidate feature. Faster to train, often matches RF accuracy, and complements RF in a stacked ensemble.
8. Common Pitfalls
Using "n_estimators too low" (B=10) and calling it "Random Forest." RF only beats single DT at B large enough for averaging to kick in. Start at B=100 minimum.
Setting max_features = d (all features) in RF. You recover plain Bagging, losing the decorrelation benefit. Use sqrt(d) for classification, d/3 for regression.
Forgetting to shuffle / class-stratify when bagging on imbalanced data. Bootstrap replicates from a 99/1 dataset are often ~99/1 themselves! Use class_weight='balanced_subsample' in scikit-learn.
Using OOB predictions for hyperparameter tuning on tiny (n < 500) datasets. OOB has higher variance at small n — stick to stratified 5-fold CV instead.
Comparing RF (n=500) against a single DT (n_estimators=1) on speed and concluding "RF is slow." Compare apples to apples: accuracy at fixed compute budget. RF nearly always wins that comparison.
Deep-pruning max_depth in RF "to prevent overfit." RF's averaging already handles variance! Leave depth unlimited (the default) and tune m_try and/or n_estimators first.